2.1 Hierarchical Vector Quantization

2.1.3 Quantization Error

Let us try to understand quantization error with an example.

Figure 1: The Voronoi tessellation for level 1 shown for the 5 cells with the points overlayed

An example of a 2 dimensional VQ is shown above.

In the above image, we can see 5 cells with each cell containing a certain number of points. The centroid for each cell is shown in blue. These centroids are also known as codewords since they represent all the points in that cell. The set of all codewords is called a codebook.

Now we want to calculate quantization error for each cell. For the sake of simplicity, let’s consider only one cell having centroid A and m data points \(F_i\) for calculating quantization error.

For each point, we calculate the distance between the point and the centroid.

\[ d = ||A - F_i||_{p} \]

In the above equation, p = 1 means L1_Norm distance whereas p = 2 means L2_Norm distance. In the package, the L1_Norm distance is chosen by default. The user can pass either L1_Norm, L2_Norm or a custom function to calculate the distance between two points in n dimensions.

\[QE = \max_i(||A-F_i||_{p})\]

Now, we take the maximum calculated distance of all m points. This gives us the furthest distance of a point in the cell from the centroid, which we refer to as Quantization Error. If the Quantization Error is higher than the given threshold, the centroid/ codevector is not a good representation for the points in the cell. Now we can perform further Vector Quantization on these points and repeat the above steps.

Please note that the user can select mean, max or any custom function to calculate the Quantization Error. The custom function takes a vector of m value (where each value is a distance between point in n dimensions and centroids) and returns a single value which is the Quantization Error for the cell.

If we select mean as the error metric, the above Quantization Error equation will look like this:

\[QE = \frac{1}{m}\sum_{i=1}^m||A-F_i||_{p}\]

6.1 Step 1: Data Compression

The core function for compression in the workflow is HVQ, which is called within the HVT function. we have a parameter called quantization error. This parameter acts as a threshold and determines the number of levels in the hierarchy. It means that, if there are ‘n’ number of levels in the hierarchy, then all the clusters formed till this level will have quantization error equal or greater than the threshold quantization error. The user can define the number of clusters in the first level of hierarchy and then each cluster in first level is sub-divided into the same number of clusters as there are in the first level. This process continues and each group is divided into smaller clusters as long as thethreshold quantization error is met. The output of this technique will be hierarchically arranged vector quantized data.

However, let’s try to comprehend the HVT function first before moving on.

HVT(
  dataset,
  min_compression_perc,
  n_cells,
  depth,
  quant.err,
  projection.scale,
  normalize = T,
  distance_metric = c("L1_Norm", "L2_Norm"),
  error_metric = c("mean", "max"),
  quant_method = c("kmeans", "kmedoids"),
  diagnose = TRUE,
  hvt_validation = FALSE,
  train_validation_split_ratio = 0.8
)

Each of the parameters of HVT function have been explained below:

• dataset - A dataframe with numeric columns.

• min_compression_perc - An integer indicating the minimum percent compression rate to be achieved for the dataset.

• n_cells - An integer indicating the number of cells per hierarchy (level).

• depth - An integer indicating the number of level. (1 = No hierarchy, 2 = 2 level, etc …).

• quant.error - A number indicating the quantization error threshold. A cell will only breakdown into further cells if the quantization error of the cell is above the defined quantization error threshold.

• projection.scale - A number indicating the scale factor for the tesselations so as to visualize the sub-tesselations well enough.

• scale_summary - A list with mean and standard deviation values for all the features in the dataset. Pass the scale summary when the input dataset is already scaled or normalize is set to False.

• distance_metric - The distance metric can be L1_Norm or L2_Norm. L1_Norm is selected by default. The distance metric is used to calculate the distance between an n dimensional point and centroid. The user can also pass a custom function to calculate this distance.

• error_metric - The error metric can be mean or max. max is selected by default. max will return the max of m values and mean will take mean of m values where each value is a distance between a point and centroid of the cell. Moreover, the user can also pass a custom function to calculate the error metric.

• quant_method - The quantization method can be kmeans or kmedoids. kmeans is selected by default.

• normalize - A logical value indicating whether the columns in your dataset need to be normalized. Default value is TRUE. The algorithm supports Z-score normalization.

• diagnose - A logical value indicating whether user wants to perform diagnostics on the model. Default value is TRUE.

• hvt_validation - A logical value indicating whether user wants to holdout a validation set and find mean absolute deviation of the validation points from the centroid. Default value is FALSE.

• train_validation_split_ratio - A numeric value indicating train validation split ratio. This argument is only used when hvt_validation has been set to TRUE. Default value for the argument is 0.8.

We will use the HVT function to compress our data while preserving essential features of the dataset. Our goal is to achieve data compression upto atleast 80%. In situations where the compression ratio does not meet the desired target, we can explore adjusting the model parameters as a potential solution. This involves making modifications to parameters such as the quantization error threshold or increasing the number of cells and then rerunning the HVT function again.

In our example we will iteratively increase the number of cells until the desired compression percentage is reached instead of increasing the quantization threshold because it may reduce the level of detail captured in the data representation

Iteration 1:

We will pass the below mentioned model parameters along with torus dataset to HVT function.

Model Parameters

• Number of Cells at each Level = 100
• Maximum Depth = 1
• Quantization Error Threshold = 0.1
• Error Metric = Max
• Distance Metric = Manhattan

set.seed(240)
hvt.torus <- muHVT::HVT(
  torus_df,
  n_cells = 100,
  depth = 1,
  quant.err = 0.1,
  projection.scale = 10,
  normalize = F,
  distance_metric = "L1_Norm",
  error_metric = "max",
  quant_method = "kmeans"
)

Let’s checkout the compression summary.

compressionSummaryTable(hvt.torus[[3]]$compression_summary)

As it can be seen from the table above, none of the 100 cells have reached the quantization threshold error. Therefore we can further subdivide the cells by increasing the n_cells parameters and then see if desired compression (80%) is reached

Iteration 2:

Let’s retry by increasing the n_cells parameter to 300.

Model Parameters

• Number of Cells at each Level = 300
• Maximum Depth = 1
• Quantization Error Threshold = 0.1
• Error Metric = Max
• Distance Metric = Manhattan

set.seed(240)
hvt.torus2 <- muHVT::HVT(
  torus_df,
  n_cells = 300,
  depth = 1,
  quant.err = 0.1,
  projection.scale = 10,
  normalize = F,
  distance_metric = "L1_Norm",
  error_metric = "max",
  quant_method = "kmeans"
)

Let’s checkout the compression summary again.

compressionSummaryTable(hvt.torus2[[3]]$compression_summary)

It can be observed from the table above that only 5 cells out of 300 i.e. 2% of the cells reached the Quantization Error threshold. Therefore we can further subdivide the cells by increasing the n_cells parameters and then see if 80% compression is reached

Iteration 3:

Since we are yet to achieve the compression of atleast 80%, lets try again by increasing the n_cells parameter to 900.

Model Parameters

• Number of Cells at each Level = 900
• Maximum Depth = 1
• Quantization Error Threshold = 0.1
• Error Metric = Max
• Distance Metric = Manhattan

set.seed(240)
hvt.torus3 <- muHVT::HVT(
  torus_df,
  n_cells = 900,
  depth = 1,
  quant.err = 0.1,
  projection.scale = 10,
  normalize = F,
  distance_metric = "L1_Norm",
  error_metric = "max",
  quant_method = "kmeans"
)

Let’s check the compression summary for torus.

compressionSummaryTable(hvt.torus3[[3]]$compression_summary)

By increasing the number of cells to 900, we were successfully able to compress 85% of the data, so we will not further subdivide the cells

We successfully compressed 85% of the data using n_cells parameter as 900, the next step involves performing data projection on the compressed data. In this step, the compressed data will be transformed and projected onto a lower-dimensional space to visualize and analyze the data in a more manageable form.

6.2 Step 2: Data Projection

The function sammonsProjection() utilizes the sammons function from the MASS package being called in HVT. Sammon’s projection is an algorithm that maps a high-dimensional space to a space of lower dimensionality while attempting to preserve the structure of inter-point distances in the projection.The centroids are plotted in 2D after performing Sammon’s projection at every level of the tessellation.

Iteration 1

lets view the projected 2D coordinates after performing sammon’s projection on the compressed data for the first iteration where we set n_cells parameter as 100. For the shake of brevity we are displaying first six rows.

hvt_torus_coordinates <-hvt.torus[[2]][[1]][["1"]]
centroids <<- list()
  coordinates_value <- lapply(1:length(hvt_torus_coordinates), function(x){
    centroids <-hvt_torus_coordinates[[x]]
    coordinates <- centroids$pt
  })
centroid_coordinates<<- do.call(rbind.data.frame, coordinates_value)  
colnames(centroid_coordinates) <- c("x_coord","y_coord")
centroid_coordinates$Row.No <- as.numeric(row.names(centroid_coordinates)) 
centroid_coordinates <- centroid_coordinates %>% dplyr::select(Row.No,x_coord,y_coord)
centroid_coordinates1 <- centroid_coordinates %>% data.frame() %>% round(4)
Table(head(centroid_coordinates1), scroll = T, limit = 20)

Lets see the projected Sammons 2D onto a plane with n_cell set to 100 in first iteration.

ggplot(centroid_coordinates1, aes(x_coord, y_coord)) +
  geom_point(color = "blue") +
  labs(x = "X", y = "Y")

Figure 3: Sammons 2D Plot for 100 cells

Iteration 2

lets view the projected 2D coordinates after performing sammon’s projection on the compressed data for the Second iteration where we set n_cells parameter as 300. For the shake of brevity we are displaying first six rows.

hvt_torus_coordinates <-hvt.torus2[[2]][[1]][["1"]]
centroids <<- list()
  coordinates_value <- lapply(1:length(hvt_torus_coordinates), function(x){
    centroids <-hvt_torus_coordinates[[x]]
    coordinates <- centroids$pt
  })
centroid_coordinates<<- do.call(rbind.data.frame, coordinates_value)  
colnames(centroid_coordinates) <- c("x_coord","y_coord")
centroid_coordinates$Row.No <- as.numeric(row.names(centroid_coordinates)) 
centroid_coordinates <- centroid_coordinates %>% dplyr::select(Row.No,x_coord,y_coord)
centroid_coordinates2 <- centroid_coordinates %>% data.frame() %>% round(4)
Table(head(centroid_coordinates2), scroll = T, limit = 20)

Lets see the projected Sammons 2D onto a plane with n_cell set to 300 in second iteration.

ggplot(centroid_coordinates2, aes(x_coord, y_coord)) +
  geom_point(color = "blue") +
  labs(x = "X", y = "Y")

Figure 4: Sammons 2D Plot for 300 cells

Iteration 3

lets view the projected 2D coordinates after performing sammon’s projection on the compressed data for the third iteration where we set n_cells parameter as 900. For the shake of brevity we are displaying first six rows.

hvt_torus_coordinates <-hvt.torus3[[2]][[1]][["1"]]
centroids <<- list()
  coordinates_value <- lapply(1:length(hvt_torus_coordinates), function(x){
    centroids <-hvt_torus_coordinates[[x]]
    coordinates <- centroids$pt
  })
centroid_coordinates<<- do.call(rbind.data.frame, coordinates_value)  
colnames(centroid_coordinates) <- c("x_coord","y_coord")
centroid_coordinates$Row.No <- as.numeric(row.names(centroid_coordinates)) 
centroid_coordinates <- centroid_coordinates %>% dplyr::select(Row.No,x_coord,y_coord)
centroid_coordinates3 <- centroid_coordinates %>% data.frame() %>% round(4)
Table(head(centroid_coordinates3), scroll = T, limit = 20)

Lets see the projected Sammons 2D onto a plane with n_cell set to 900 in third iteration.

ggplot(centroid_coordinates3, aes(x_coord, y_coord)) +
  geom_point(color = "blue") +
  labs(x = "X", y = "Y")

Figure 5: Sammons 2D Plot for 900 cells

6.3 Step 3: Tessellation

The deldir package computes the Delaunay triangulation (and hence the Dirichlet or Voronoi tessellation) of a planar point set according to the second (iterative) algorithm of Lee and Schacter. For subsequent levels, transformation is performed on the 2D coordinates to get all the points within its parent tile. Tessellations are plotted using these transformed points as centroids.plotHVT is the main function to plot hierarchical voronoi tessellation.

Now let’s try to understand plotHVT function. The parameters have been explained in detail below:

plotHVT(hvt.results, line.width, color.vec, pch1 = 21, centroid.size = 3, title = NULL, maxDepth = 1)

• hvt.results - A list containing the output of the HVT function which has the details of the tessellations to be plotted.

• line.width - A vector indicating the line widths of the tessellation boundaries for each layer.

• color.vec - A vector indicating the colors of the tessellations boundaries at each layer.

• pch1 - Symbol type of the centroids of the tessellations (parent levels). Refer points (default = 21).

• centroid.size - Size of centroids of first level tessellations (default = 3).

• title - Set a title for the plot (default = NULL).

• maxDepth - An integer indicating the number of levels. (default = NULL)

Iteration 1

To enhance visualization, let’s generate a plot of the Voronoi tessellation for the first iteration where we set n_cells parameter as 100. This plot will provide a visual representation of the Voronoi regions corresponding to the data points, aiding in the analysis and understanding of the data distribution.

muHVT::plotHVT(
  hvt.torus,
  line.width = c(0.4),
  color.vec = c("#141B41"),
  centroid.size = 0.6,
  maxDepth = 1
)

Figure 6: The Voronoi tessellation for layer 1 shown for the 100 cells in the dataset ’torus’

Iteration 2

Now, let’s plot the Voronoi tessellation for the second iteration where we set n_cells parameter to 300.

muHVT::plotHVT(
  hvt.torus2,
  line.width = c(0.4),
  color.vec = c("#141B41"),
  centroid.size = 0.6,
  maxDepth = 1
)

Figure 7: The Voronoi tessellation for layer 1 shown for the 300 cells in the dataset ’torus’

Iteration 3

Now, let’s plot the Voronoi tessellation again, for the third iteration where we set n_cells parameter to 900.

muHVT::plotHVT(
  hvt.torus3,
  line.width = c(0.4),
  color.vec = c("#141B41"),
  centroid.size = 0.6,
  maxDepth = 1
)

Figure 8: The Voronoi tessellation for layer 1 shown for the 900 cells in the dataset ’torus’

From the presented plot, the inherent structure of the donut can be easily observed in the two-dimensional space

We will now overlay all the features as heatmap over the Voronoi Tessellation plot for better visualization and identification of patterns, trends, and variations in the data.

Heat Maps

Let’s have look at the hvtHmap function which we will use to overlay a variable as heatmap.

hvtHmap(hvt.results, dataset, child.level, hmap.cols, color.vec ,line.width, palette.color = 6)

• hvt.results - A list of results obtained from the HVT function.

• dataset - A dataframe containing the variables to overlay as a heatmap. The user can pass an external dataset or the dataset that was used to perform hierarchical vector quantization. The dataset should have the same number of points as the dataset used to perform hierarchical Vector Quantization in the HVT function.

• child.level - A number indicating the level for which the heat map is to be plotted.

• hmap.cols - The column number of column name from the dataset indicating the variables for which the heat map is to be plotted. To plot the quantization error as heatmap, pass 'quant_error'. Similarly to plot the no of points in each cell as heatmap, pass 'no_of_points' as a parameter.

• color.vec - A color vector such that length(color.vec) = child.level (default = NULL).

• line.width - A line width vector such that length(line.width) = child.level (default = NULL).

• palette.color - A number indicating the heat map color palette. 1 - rainbow, 2 - heat.colors, 3 - terrain.colors, 4 - topo.colors, 5 - cm.colors, 6 - BlCyGrYlRd (Blue,Cyan,Green,Yellow,Red) color (default = 6).

• show.points - A boolean indicating whether the centroids should be plotted on the tessellations (default = FALSE).

Now let’s plot the Voronoi Tessellation with the heatmap overlaid for all the features in the torus data for better visualization and interpretation of data patterns and distributions.

The heatmaps displayed below provides a visual representation of the spatial characteristics of the torus, allowing us to observe patterns and trends in the distribution of each of the features (n,X,Y and Z). The sheer green shades highlight regions with higher coordinate values in each of the heatmaps, while the indigo shades indicate areas with the lowest coordinate values in each of the heatmaps. By analyzing these heatmaps, we can gain insights into the variations and relationships between each of these features within the torus structure.

muHVT::hvtHmap(
  hvt.torus3,
  torus_df,
  child.level = 1,
  hmap.cols = "n",
  line.width = c(0.4),
  color.vec = c("#141B41"),
  palette.color = 6,
  centroid.size = 0.8,
  show.points = T,
  quant.error.hmap = 0.1,
  n_cells.hmap = 15
)

Figure 9: The Voronoi tessellation for layer 1 and number of cells 900 with the heat map overlaid for No. of entities in each cell in the ’torus’ dataset

muHVT::hvtHmap(
  hvt.torus3,
  torus_df,
  child.level = 1,
  hmap.cols = "x",
  line.width = c(0.4),
  color.vec = c("#141B41"),
  palette.color = 6,
  centroid.size = 0.8,
  show.points = T,
  quant.error.hmap = 0.1,
  n_cells.hmap = 15
)

Figure 10: The Voronoi tessellation for layer 1 and number of cells 900 with the heat map overlaid for variable x in the ’torus’ dataset

muHVT::hvtHmap(
  hvt.torus3,
  torus_df,
  child.level = 1,
  hmap.cols = "y",
  line.width = c(0.4),
  color.vec = c("#141B41"),
  palette.color = 6,
  centroid.size = 0.8,
  show.points = T,
  quant.error.hmap = 0.1,
  n_cells.hmap = 15
)

Figure 11: The Voronoi tessellation for layer 1 and number of cells 900 with the heat map overlaid for variable y in the ’torus’ dataset

muHVT::hvtHmap(
  hvt.torus3,
  torus_df,
  child.level = 1,
  hmap.cols = "z",
  line.width = c(0.4),
  color.vec = c("#141B41"),
  palette.color = 6,
  centroid.size = 0.8,
  show.points = T,
  quant.error.hmap = 0.1,
  n_cells.hmap = 15
)

Figure 12: The Voronoi tessellation for layer 1 and number of cells 900 with the heat map overlaid for variable z in the ’torus’ dataset

6.4 Step 4: Prediction(predictHVT)

Raw Testing Dataset

Lets have a look at out test dataset containing (3000 points) before we pass it to predictHVT function for scoring.

Table(head(test_dataset1))

However, let’s try to comprehend the predictHVT function first before moving on

predictHVT(data,
                  hvt.results,
                  hmap.cols = NULL,
                  child.level = 1,
                  ...)

The important parameters for the function predictHVT are as below:

• data - A dataframe containing the test dataset. The dataframe should have atleast one variable used for training. The variables from this dataset can also be used to overlay as heatmap

• hvt.results - A list of hvt.results obtained from the HVT function while performing hierarchical vector quantization on training data

• hmap.cols - The column number of column name from the dataset indicating the variables for which the heat map is to be plotted. A heatmap won’t be plotted if NULL is passed (Default = NULL)

• child.level - A number indicating the level for which the heat map is to be plotted (Only used if hmap.cols is not NULL)

• normalize - A logical value indicating if the columns in your dataset should be normalized. Default value is TRUE.

• distance_metric - The distance metric can be ’Euclidean” or “Manhattan”. Euclidean is selected by default.

• error_metric - The error metric can be “mean” or “max”. mean is selected by default

• yVar - Name of the dependent variable(s)

• ... - color.vec and line.width can be passed from here

Now once we have built the model, let us try to predict using our test dataset which cell and which level each point belongs to.

set.seed(240)
predictions_torus <- muHVT::predictHVT(
  testTorus,
  hvt.torus3,
  child.level = 1,
  line.width = c(1.2),
  color.vec = c("#141B41"),
  quant.error.hmap = 0.1,
  n_cells.hmap = 9000,
  normalize = F
)

Let’s see which cell and level each point belongs to and check the mean absolute difference. For the sake of brevity, we will only show the first 10 rows

data1 <- test_dataset
data1$Row.No <- row.names(test_dataset)
data1 <- data1 %>% dplyr::select(Row.No,x,y,z)
rownames(data1) <- NULL
colnames(data1) <- c("Row.No","x_act","y_act","z_act")
data2 <- predictions_torus[["scoredPredictedData"]]
data2 <- data2 %>% dplyr::select(Cell.ID,x,y,z)
colnames(data2) <- c("Cell.ID","x_pred","y_pred","z_pred")
combined <- cbind(data1,data2)
combined$diff <- rowMeans(abs(combined[, c("x_act", "y_act", "z_act")] - combined[, c("x_pred", "y_pred", "z_pred")]))
options(scipen = 999)
combined %>% head(100) %>% 
  as.data.frame() %>%
  Table(scroll = T, limit = 10)

hist(combined$diff, breaks = 20, col = "blue", main = "Mean Absolute Difference", xlab = "Difference")

Figure 13: Mean Absolute Difference

7.1 Step 1: Data Compression

For more detailed information on Data Compression please refer to section 2 of this vignette.

We will use the HVT function to compress our data while preserving essential features of the dataset. Our goal is to achieve data compression upto atleast 80%. In situations where the compression ratio does not meet the desired target, we can explore adjusting the model parameters as a potential solution. This involves making modifications to parameters such as the quantization error threshold or increasing the number of cells and then rerunning the HVT function again.

In our example we will iteratively increase the number of cells until the desired compression percentage is reached instead of increasing the quantization threshold because it may reduce the level of detail captured in the data representation

We will pass the below mentioned model parameters along with computers dataset to HVT function.

Model Parameters

• Number of Cells at each Level = 440
• Maximum Depth = 1
• Quantization Error Threshold = 0.2
• Error Metric = Max
• Distance Metric = Manhattan

set.seed(240)
hvt.results <- list()
hvt.results <- muHVT::HVT(trainComputers,   
                          n_cells = 440,
                          depth = 1,
                          quant.err = 0.2,
                          projection.scale = 10,
                          normalize = T,
                          distance_metric = "L1_Norm",
                          error_metric = "max",
                          quant_method = "kmeans",
                          diagnose = F)

Now let’s check the compression summary. The table below shows no of cells, no of cells having quantization error below threshold and percentage of cells having quantization error below threshold for each level.

compressionSummaryTable(hvt.results[[3]]$compression_summary)

As it can be seen from the table above, 81% of the cells have reached the quantization threshold error. Since we are successfully able to attain the desired compression percentage, so we will not further subdivide the cells

hvt.results[[3]] gives us detailed information about the hierarchical vector quantized data.

hvt.results[[3]][['summary']] gives a nice tabular data containing no of points, Quantization Error and the codebook.

The datatable displayed below is the summary from hvt.results

summaryTable(hvt.results[[3]]$summary)